Міністерство освіти Республіки Білорусь
Установа освіти
«Гомельський державний університет ім. Ф. Скорини »
Математичний факультет
Кафедра МПМ
Реферат
Генерація комбінаторних об'єктів
Виконавець:
Студентка групи М-43
Самусенко А.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент
Лебедєва М.Т.
Гомель 2007
Зміст
Введення ................................................. .................................................. ........ 3
1 Безліч всіх підмножин .............................................. ........................ 4
2 Перестановки ................................................ ................................................ 7
3 Сполучення ................................................ .................................................. .. 11
4 Розміщення ................................................ ................................................. 14
5 Перестановки з повтореннями .............................................. ..................... 17
6 Сполучення з повтореннями .............................................. ........................... 20
Висновок ................................................. .................................................. . 23
Література ................................................. .................................................. .. 24
Введення
Існує набір завдань, вирішення яких полягає в генерації всіх елементів таких комбінаторних об'єктів як безліч всіх підмножин, перестановки, поєднання, розміщення, перестановки з повтореннями, поєднання з повтореннями.
Для кожного згенерованого елемента потім перевіряються якісь властивості для конкретного завдання.
У подальшому в цій роботі пропонується наступний порядок викладу матеріалу для кожного комбінаторного об'єкта: приклад, алгоритм, програма, коментарі до програми.
1 Безліч всіх підмножин
Нехай ми маємо безліч з 4-х компонент - які ми позначаємо латинськими літерами A, B, C, D відповідно.
І нехай за умовами задачі потрібно вибрати підмножина, що складається з кількох компонент, що володіє деякими властивістю. Пропонується такий спосіб вирішення завдання: ми генеруємо ВСІ можливі підмножини даної множини і для кожного з згенерованих підмножин перевіряємо чи задовольняє воно заданому властивості. Альтернативний варіант завдання - підрахувати ВСІ підмножини даної множини, що володіють заданою властивістю.
Наприклад:
Для безлічі з 4-х символів A, B, C, D безліч всіх підмножин включає в себе наступні множини:
Порожня множина
Одноелементні множини: {A}, {B}, {C}, {D}
Двохелементний безлічі: {A, B}, {A, C}, {A, D} {B, C}, {B, D}, {C, D}
Трьохелементний безлічі: {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}
Четирехелементное безліч: {A, B, C, D}
У разі, якщо порядок генерації підмножин не грає ролі (а, наприклад, у разі необхідності підрахувати всі підмножини, що володіють заданою властивістю, так воно і є) один з найбільш просто кодованих алгоритмів генерації безлічі всіх підмножин виглядає наступним чином.
Заведемо вектор B, що складається з чотирьох чисел, кожне з яких може приймати значення 0 або 1. І будемо вважати, що значення 1 вказує на те, що відповідний за номером компонент вихідного безлічі включається в множину, а значення 0 вказує на те, що елемент не включається.
Розглянемо тепер послідовність двійкових чисел від 0 до 15 і відповідні їм підмножини:
4321
DCBA
0000 - порожня множина
0001 A
0010 B
0011 AB
0100 C
0101 AC
0110 BC
0111 ABC
1000 D
1001 AD
1010 BD
1011 ABD
1100 CD
1101 ACD
1110 BCD
1111 ABCD
Таким чином, всього є 16 різних підмножин множини з 4-х елементів. У загальному випадку множина всіх підмножин множини з N елементів містить 2N (два у степені N) елементів.
Алгоритм, що забезпечує таку генерацію безлічі всіх підмножин з N елементів, може бути неформально описаний таким чином:
Формуємо масив, що складається з N нулів - і розглядаємо його як порожня множина. Таким чином, початкове значення поточного підмножини - порожня множина.
Для отримання наступного підмножини з поточного підмножини обробляємо поточний масив з чисел 0 або 1 наступним чином:
Праворуч (від першого елемента масиву до останнього) шукаємо перше число, рівне нулю.
Якщо таке число не знайдено - значить, поточний підмножина є останнім - множиною, що складається з усіх елементів, і на цьому алгоритм закінчує свою роботу.
Якщо ж елемент рівний 0 знайдений, то він замінюється на 1, а всі числа праворуч від нього (якщо такі є) замінюються на нулі.
Більш формалізовано цей алгоритм може бути записаний таким чином:
Введення (N)
Обнулення масиву B з N +1 елемента
Висновок (порожня множина)
Поки B [N +1] = 0
i = 1
Поки B [i] = 1 робити B [i] = 0, i = i +1
B [i] = 1
Висновок (множини, що визначається масивом B)
Нижче наводиться текст програми, яка зчитує N - кількість елементів у множині і виводить на екран безліч всіх підмножин позначаючи елементи відповідними по порядку латинськими літерами:
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i: byte;
begin
readln (N);
for i: = 1 to N +1 do b [i]: = 0;
writeln ('Порожня множина');
while (b [N +1] = 0) do
begin
i: = 1;
while B [i] = 1 do
begin B [i]: = 0; inc (i); end;
B [i]: = 1;
for i: = 1 to n do
if b [i] = 1 then write (alphabet [i]);
writeln;
end;
end.
При необхідності обробляти (аналізувати) побудовані підмножини можуть бути додані виклики процедур обробки, які отримують в якості параметра масив B (вказує своїми поодинокими елементами номери елементів безлічі, включених до поточне підмножина).
2 Перестановки
Нехай ми маємо 4 компоненти, позначені літерами A, B, C, D відповідно.
Тоді множина всіх перестановок з цих компонент буде включати наступні елементи:
ABCD BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADBC BDAC CDAB DCAB
ADCB BDCA CDBA DCBA
Проілюструємо спочатку алгоритм побудови наступної перестановки на прикладі перестановок з 9 компонент, позначених відповідно цифрами від 1 до 9.
Перша з таких перестановок це
1 2 3 4 5 6 7 8 9
Нехай поточна перестановка з 9 компонент:
1 9 5 8 4 7 6 3 2
Яким буде таке значення перестановки, якщо ми будуємо її в лексикографічному порядку (тобто в порядку зростання величини числа, складеного з цих цифр)?
Правильна відповідь така:
1 9 5 8 6 2 3 4 7
Як він виходить?
Перш за все, необхідно переглядати вихідний масив від кінця до початку, що б знайти перше число, яке МЕНШЕ попереднього в нашому випадку - це 4
(7> 6> 3> 2, а 4 <7)
Далі серед переглянутих чисел праворуч від знайденої 4 ми шукаємо останнє число яке більше 4. Це число 6.
(7> 4, 6> 4, 3 <4, 2 <4)
Потім міняємо ці 2 знайдених числа (4 і 6) місцями, отримуємо:
1 9 5 8 6 7 4 3 2
І тепер числа (праворуч від 6), які становлять убуваючу послідовність (7 4 3 2), попарно міняємо місцями так, що б вони склали зростаючу послідовність (2 3 4 7):
1 9 5 8 6 2 3 4 7
Це і є наступна перестановка.
А яка перестановка буде останньою для даного прикладу?
Сподіваюся, що вдумливий читач здогадався і сам:
9 8 7 6 5 4 3 2 1
Кілька неформально алгоритм побудови наступної перестановки за поточною може бути записаний таким чином:
1. Від кінця до початку перестановки шукаємо перший елемент B [i] такий, що B [i] <B [i +1] запам'ятовуємо його індекс - I
2. Від елемента I +1 до кінця шукаємо останній елемент, більший ніж B [i], запам'ятовуємо його індекс - K
3. Міняємо місцями ці елементи - з номерами I і K
4. Всю групу елементів від i +1- го елемента до N-го попарно міняємо місцями (i +1- ий елемент з N-им, i +2- ой елемент з N-1-им і т.д.)
Формалізовано алгоритм генерації всіх перестановок з N елементів може бути записаний таким чином:
Введення N
Прописуємо масив B послідовно числами від 1 до N
Це перша - початкова - перестановка, виводимо її
Поки (істина)
i = N
Поки (i> 0) і (B [i]> = B [i +1]), i = i-1
Якщо i = 0 то кінець роботи
Для j від i +1 до N
якщо B [j]> B [i] то K = j
Обмін значень B [i] і B [k]
Для j від i +1 до (i + ((N +1- i) div 2))
Обмін значень B [j] і B [N + i +1- j]
Висновок поточної перестановки B
Зрозуміло, що цикл попарних перестановок "хвоста" масиву B не можна робити від i +1 до N-го елемента - інакше елементи поміняються місцями по 2 рази - і вийти, що нічого не змінилося. Цикл потрібно виконати для половини цього "хвоста". Цьому і служить декілька складний для розуміння значення кінцевої змінної циклу: i + (N +1- i) div 2
Нижче наводиться програма, що генерує всі перестановки з N компонент, позначених N першими літерами латинського алфавіту.
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i, j, k: byte;
Procedure SwapB (i, k: byte);
var x: byte;
begin
x: = B [i]; B [i]: = B [k]; B [k]: = x;
end;
Procedure WriteB;
begin
for i: = 1 to N do write ({alphabet [b [i]]);
writeln;
end;
begin
readln (N);
for i: = 1 to N do b [i]: = i;
WriteB;
while (true) do
begin
i: = N;
while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;
if i = 0 then exit;
for j: = i +1 to N do
if (B [j]> B [i]) then K: = j;
SwapB (i, k);
for j: = i +1 to (i + ((N +1- i) div 2))
do SwapB (j, N + i +1- j);
writeB;
end;
end.
У програмі введено 2 процедури WriteB і SwapB.
Процедура WriteB викликається кожного разу, коли побудована чергова перестановка. У даній програмі процедура WriteB просто виводить відповідну послідовність латинських літер.
Процедура SwapB (i, k) введена для спрощення розуміння головної програми. SwapB просто обмінює значеннями два елементи масиву B - ті, які мають індекси, що відповідають значенням параметрів процедури i і k.
Процедура SwapB використовується в тексті програми два рази
1) При обміні значеннями двох знайдених елементів з індексами I і K.
2) При забезпеченні попарного обміну елементів "хвоста", в якому поточний елемент з індексом j обмінюється місцями зі своїм "партнером", що знаходиться на позиції N + i +1- j. Таким чином, I +1- ий елемент поміняється (при J = I +1) місцями з N-м елементом, I +2- ий елемент (при J = I +2) з N-1-им і т.д.
Загальне число перестановок з N елементів одно N! (Читається N факторіал). Нагадаємо, що N! = 1 * 2 * 3 *...* N
3 Сполучення
Нехай маємо 5 компонент, позначених латинськими літерами A, B, C, D, E відповідно.
Тоді всі сполучення з цих 5 компонент по 3, виписані в лексикографічному порядку (для літер і цифр від 1 до 5) будуть такі:
ABC 123
ABD 124
ABE 125
ACD 134
ACE 135
ADE 145
BCD 234
BCE 235
BDE 245
CDE 345
Неформально алгоритм генерації послідовності чисел у лексикографічному порядку можна записати наступним чином. Виберемо найменші M з наявних N чисел і випишемо їх у порядку зростання - і випишемо їх у порядку зростання - 1 2 3 - це початкове поєднання. Очевидно, що найбільші M чисел з наявних (3 4 5), виписані в порядку зростання, складуть останнє поєднання.
Для того, що б за поточним поєднанню отримувати наступне, можна поступати таким чином:
Знаходимо позицію в поточному поєднанні, на якій не варто останнє з можливих значень, і потім збільшуємо його на 1. А всі наступні елементи поєднання отримуємо збільшенням на 1 попереднього елемента поєднання.
Наприклад нехай поточне поєднання
1 3 5
Аналіз починаємо з останньої позиції поєднання.
5 - це останнє можливе значення, тому переходимо до попередньої позиції. 3 - це не останнє можливе значення для цієї позиції (яким є 4 в даному випадку). Тому ми його збільшуємо на 1 - отримуємо 4. А число в такій позиції отримуємо додатком 1 до цієї 4-ці - і отримуємо 5. Таким чином таке значення буде 1 4 5
Більш формалізовано цей алгоритм може бути записаний таким чином:
Введення N, M (з скільки, на скільки)
Заносимо в масив B числа від 1 до M
Це перше поєднання, виводимо його
Поки (істина)
i = M
Поки (i> 0) і (b [i] = N-m + i), i = i-1
Якщо i = 0 то робота завершена
B [i] = B [i] +1
Для j від i +1 до MB [j] = B [j-1] +1;
Висновок B - наступної перестановки
Нижче наводиться програма, яка зчитує з клавіатури значення N і M і виводить у лексикографічному порядку всі поєднання з N перший латинських літер за M.
uses crt;
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, M, i, j, k: byte;
Procedure WriteB;
begin
for i: = 1 to M do write (alphabet [b [i]]);
writeln;
end;
begin
readln (N, M);
for i: = 1 to M do b [i]: = i;
WriteB;
while (true) do
begin
i: = M;
while (i> 0) and (b [i] = N-m + i) do Dec (i);
if i = 0 then exit;
Inc (B [i]);
for j: = i +1 to M do B [j]: = B [j-1] +1;
WriteB;
end;
end.
Нагадаємо, що загальна кількість сполучень з N елементів по M може бути обчислено за формулою C (N, M) = N! / (M! * (NM)!)
4 Розміщення
Для генерації всіх розміщень з N елементів з M можна скористатися композицією алгоритмів, викладених вище. Тобто генерувати всі сполучення з N з M, а потім для кожного отриманого поєднання генерувати всі перестановки з M елементів.
Наприклад, при генерації всіх розміщень з 5 елементів по 3, у випадку, якщо самі елементи позначені латинськими літерами A, B, C, D, E потрібно отримати наступну послідовність, представлену для компактності у вигляді 10 рядків, кожна з яких представляє всі можливі поєднання з 3 букв першого елемента рядка. А самі перші елементи рядків якраз і представляють всі можливі поєднання з 5 літер по 3.
ABC ACB BAC BCA CAB CBA
ABD ...
ABE ...
ACD ...
ACE ...
ADE ...
BCD ...
BCE ...
BDE ...
CDE CED DCE DEC ECD EDC
Загальна кількість pазмещеній - з N елементів по M може бути
знайдено за формулою:
N! / (NM)!
Нижче наводиться програма, яка вводить з клавіатури числа N, M і генерує всі можливі розміщення з N літер за M.
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
type
barray = array [1 .. 100] of byte;
var
b: barray;
N, M, i, j, k: byte;
z: longint;
Procedure WriteB (B: barray);
begin
Inc (Z); Write (Z: 3, ':');
for i: = 1 to M do write (alphabet [b [i]]);
writeln;
end;
Procedure SwapB (var B: barray; i, k: byte);
var x: byte;
begin
x: = B [i]; B [i]: = B [k]; B [k]: = x;
end;
Procedure PermuteAll (B: barray; N: byte);
var i, k, j: byte;
begin
WriteB (B);
while (true) do
begin
i: = N;
while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;
if i = 0 then exit;
for j: = i +1 to N do
if (B [j]> B [i]) then K: = j;
SwapB (B, i, k);
for j: = i +1 to (i + ((N +1- i) div 2)) do SwapB (B, j, N + i +1- j);
WriteB (B);
end;
end;
begin
readln (N, M);
for i: = 1 to M do b [i]: = i;
PermuteAll (B, M);
while (true) do
begin
i: = M;
while (i> 0) and (b [i] = N-m + i) do Dec (i);
if i = 0 then exit;
Inc (B [i]);
for j: = i +1 to M do B [j]: = B [j-1] +1;
PermuteAll (B, M);
end;
readln;
end.
Пояснення до програми:
1. Головна програма вводить числа N, M і генерує за описаним вище алгоритмом всі сполучення з N за M. Для кожного побудованого у векторі B поєднання викликається процедура PermuteAll, якій в якості параметрів передаються поточне поєднання B і кількість елементів у ньому M. Процедура PermuteAll генерує для отриманого поєднання всі можливі перестановки.
2. Масив B передається в процедуру PermuteAll за значенням (при оголошенні процедури при параметрі B немає ключового слова VAR) і тому зміни масиву B у процедурі PermuteAll не впливають на вміст масиву B у головній програмі.
3. У той же час для того, що б процедура SwapB могла обмінювати значення в B і повертати змінений масив в зухвалу її процедуру PermuteAll, масив B доданий в параметри процедури SwapB з передачею за адресою - використовуючи ключове слово VAR.
4. Для передачі масиву як параметра заведений спеціальний тип BARRAY.
5. Для підрахунку всіх згенерованих розміщень використовується змінна Z у процедурі WriteB.
5 Перестановки з повтореннями
Перестановки з повтореннями допускають повторне використання елементів. Наприклад, нехай маємо безліч, що складається з двох символів A та двох символів B.
Тоді всі перестановки з повтореннями з цих символів будуть такі:
AABB ABBA BABA ABAB BAAB BBAA
У загальному випадку, якщо маємо
N1 предметів 1-го виду
N2 предметів 2-го виду
...
Nk предметів K-го виду
Загальна кількість перестановок може бути обчислено за формулою
N! / (N1! * N2 !*..* Nk!)
Алгоритм аналогічний генерації перестановок без повторень за винятком формування початкової перестановки:
i = 0;
Для j від 1 до k
Для m від 1 до N [j] i = i +1; B [i] = j;
Нижче наводиться програма генерації перестановок з поверненнями. Кількість K різних типів предметів, позначених латинськими літерами вводиться з клавіатури. З клавіатури також вводяться кількості NN [j] предметів кожного типу.
Сума введених NN [j] визначає загальну кількість елементів у кожній з генеруються перестановок.
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i, j, k, m: byte;
NN: array [1 .. 100] of longint;
Procedure SwapB (i, k: byte);
var x: byte;
begin
x: = B [i]; B [i]: = B [k]; B [k]: = x;
end;
Procedure WriteB;
begin
for i: = 1 to N do write (alphabet [b [i]]);
writeln;
end;
begin
readln (K);
N: = 0;
for i: = 1 to K do
begin read (NN [i]); N: = N + NN [i]; end;
i: = 0;
for j: = 1 to k do
for m: = 1 to NN [j]
do begin Inc (i); B [i]: = j; end;
WriteB;
while (true) do
begin
i: = N;
while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;
if i = 0 then exit;
for j: = i +1 to N do if (B [j]> B [i]) then K: = j;
SwapB (i, k);
for j: = i +1 to (i + ((N +1- i) div 2)) do SwapB (j, N + i +1- j);
WriteB;
end;
end.
6 Сполучення з повтореннями
Для безлічі символів від A до C і розміру M = 3 поєднання з повтореннями будуть наступними:
CCC BCC BBC BBB ACC ABC ABB AAC AAB AAA
Загальна кількість сполучень = (N + M-1)! / (M! * (N-1)!)
де N - кількість символів
M - по скільки символів у поєднанні
Основна ідея створення таких сполучень з повтореннями полягає в наступному:
Сполучення записуємо у вигляді (N-1)-го нуля і M одиниць, де одиниці замінюють символи, а нулі виступають в pолі pазделітелей.
Наприклад:
ABB - 1 0 1 1 AAC - 1 1 0 0 1 CCC - 0 0 1 1 1
ABBAACCCC
При такому підході для вирішення завдання досить згенерувати всі перестановки з M одиниць і N-1-го нуля.
Нижче наводиться програма, яка вирішує поставлену задачу.
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i, j, k, M, N1: byte;
Procedure SwapB (i, k: byte);
var x: byte;
begin
x: = B [i]; B [i]: = B [k]; B [k]: = x;
end;
Procedure WriteB;
var i, j: byte;
begin
j: = 1;
for i: = 1 to N do
if b [i] = 0
then Inc (j)
else write (alphabet [j]);
writeln;
end;
begin
readln (N1, M); N: = N1-1 + M;
for i: = 1 to n1-1 do b [i]: = 0;
for i: = n1 to n1 + m-1 do b [i]: = 1;
WriteB;
while (true) do
begin
i: = N;
while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;
if i = 0 then exit;
for j: = i +1 to N do
if (B [j]> B [i]) then K: = j;
SwapB (i, k);
for j: = i +1 to (i + ((N +1- i) div 2)) do
SwapB (j, N + i +1- j);
WriteB;
end;
end.
Пояснення до програми:
1. Початкова перестановка формується послідовно з N1-1 нулів і M одиниць.
2. У програмі виведення перестановки WriteB здійснені зміни, відповідні задумом (нулі - роздільники, одиниці - символи). Якщо поточний елемент масиву B дорівнює 0, то "стає активним" наступний символ. Якщо поточний символ масиву B дорівнює 1, то поточний активний символ виводиться на екран.
Висновок
Всі програми для більшої наочності в якості ілюстрації оперують з масивом символів від A до Z. Очевидно, що пропоновані алгоритми та програми практично не змінюються при роботі з масивами елементів будь-якого типу, необхідної за умовами задачі (наприклад, масивами чисел, слів, геометричних фігур і т.д.)
Література
1. Абдеев Р.Ф. Філософія інформаційної цивілізації. - М.: Владос, 1994.
2. Адамар Ж. Дослідження психології процесу винаходи в галузі математики. - М.: Сов. радіо, 1970.
3. Болтянский В.Г. Інформатика і математики / / Математика в школі. 1989. № 4.-С.86-90
4. Вейценбаум Дж. Можливості обчислювальних машин і людський розум. - М.: Радіо і зв'язок, 1982.
5. Вірт Н. Алгоритми + Структури даних = Програма. - М.: Світ, 1989
6. Вірт Н. Систематичне програмування: Введення. - М.: Світ, 1977.
7. Громов Г.Р. Нариси інформаційної технології. - М.: ІнфоАрт, 1993.
8. Дейкстра Е. Дисципліна програмування. - М.: Світ, 1978.
9. Ільєнко Е. В. Філософія і культура. - М.: Політ. лит., 1991.
10. Йодан Е. Структурне проектування і конструювання програм. - М.: Світ, 1979.
11. Майерс Г. Надійність програмного забезпечення. - М.: Світ, 1980.
12. Махмутов М.І. Організація проблемного навчання в школі. - М., 1986.
Установа освіти
«Гомельський державний університет ім. Ф. Скорини »
Математичний факультет
Кафедра МПМ
Реферат
Генерація комбінаторних об'єктів
Виконавець:
Студентка групи М-43
Самусенко А.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент
Лебедєва М.Т.
Гомель 2007
Зміст
Введення ................................................. .................................................. ........ 3
1 Безліч всіх підмножин .............................................. ........................ 4
2 Перестановки ................................................ ................................................ 7
3 Сполучення ................................................ .................................................. .. 11
4 Розміщення ................................................ ................................................. 14
5 Перестановки з повтореннями .............................................. ..................... 17
6 Сполучення з повтореннями .............................................. ........................... 20
Висновок ................................................. .................................................. . 23
Література ................................................. .................................................. .. 24
Введення
Існує набір завдань, вирішення яких полягає в генерації всіх елементів таких комбінаторних об'єктів як безліч всіх підмножин, перестановки, поєднання, розміщення, перестановки з повтореннями, поєднання з повтореннями.
Для кожного згенерованого елемента потім перевіряються якісь властивості для конкретного завдання.
У подальшому в цій роботі пропонується наступний порядок викладу матеріалу для кожного комбінаторного об'єкта: приклад, алгоритм, програма, коментарі до програми.
1 Безліч всіх підмножин
Нехай ми маємо безліч з 4-х компонент - які ми позначаємо латинськими літерами A, B, C, D відповідно.
І нехай за умовами задачі потрібно вибрати підмножина, що складається з кількох компонент, що володіє деякими властивістю. Пропонується такий спосіб вирішення завдання: ми генеруємо ВСІ можливі підмножини даної множини і для кожного з згенерованих підмножин перевіряємо чи задовольняє воно заданому властивості. Альтернативний варіант завдання - підрахувати ВСІ підмножини даної множини, що володіють заданою властивістю.
Наприклад:
Для безлічі з 4-х символів A, B, C, D безліч всіх підмножин включає в себе наступні множини:
Порожня множина
Одноелементні множини: {A}, {B}, {C}, {D}
Двохелементний безлічі: {A, B}, {A, C}, {A, D} {B, C}, {B, D}, {C, D}
Трьохелементний безлічі: {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}
Четирехелементное безліч: {A, B, C, D}
У разі, якщо порядок генерації підмножин не грає ролі (а, наприклад, у разі необхідності підрахувати всі підмножини, що володіють заданою властивістю, так воно і є) один з найбільш просто кодованих алгоритмів генерації безлічі всіх підмножин виглядає наступним чином.
Заведемо вектор B, що складається з чотирьох чисел, кожне з яких може приймати значення 0 або 1. І будемо вважати, що значення 1 вказує на те, що відповідний за номером компонент вихідного безлічі включається в множину, а значення 0 вказує на те, що елемент не включається.
Розглянемо тепер послідовність двійкових чисел від 0 до 15 і відповідні їм підмножини:
4321
DCBA
0000 - порожня множина
0001 A
0010 B
0011 AB
0100 C
0101 AC
0110 BC
0111 ABC
1000 D
1001 AD
1010 BD
1011 ABD
1100 CD
1101 ACD
1110 BCD
1111 ABCD
Таким чином, всього є 16 різних підмножин множини з 4-х елементів. У загальному випадку множина всіх підмножин множини з N елементів містить 2N (два у степені N) елементів.
Алгоритм, що забезпечує таку генерацію безлічі всіх підмножин з N елементів, може бути неформально описаний таким чином:
Формуємо масив, що складається з N нулів - і розглядаємо його як порожня множина. Таким чином, початкове значення поточного підмножини - порожня множина.
Для отримання наступного підмножини з поточного підмножини обробляємо поточний масив з чисел 0 або 1 наступним чином:
Праворуч (від першого елемента масиву до останнього) шукаємо перше число, рівне нулю.
Якщо таке число не знайдено - значить, поточний підмножина є останнім - множиною, що складається з усіх елементів, і на цьому алгоритм закінчує свою роботу.
Якщо ж елемент рівний 0 знайдений, то він замінюється на 1, а всі числа праворуч від нього (якщо такі є) замінюються на нулі.
Більш формалізовано цей алгоритм може бути записаний таким чином:
Введення (N)
Обнулення масиву B з N +1 елемента
Висновок (порожня множина)
Поки B [N +1] = 0
i = 1
Поки B [i] = 1 робити B [i] = 0, i = i +1
B [i] = 1
Висновок (множини, що визначається масивом B)
Нижче наводиться текст програми, яка зчитує N - кількість елементів у множині і виводить на екран безліч всіх підмножин позначаючи елементи відповідними по порядку латинськими літерами:
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i: byte;
begin
readln (N);
for i: = 1 to N +1 do b [i]: = 0;
writeln ('Порожня множина');
while (b [N +1] = 0) do
begin
i: = 1;
while B [i] = 1 do
begin B [i]: = 0; inc (i); end;
B [i]: = 1;
for i: = 1 to n do
if b [i] = 1 then write (alphabet [i]);
writeln;
end;
end.
При необхідності обробляти (аналізувати) побудовані підмножини можуть бути додані виклики процедур обробки, які отримують в якості параметра масив B (вказує своїми поодинокими елементами номери елементів безлічі, включених до поточне підмножина).
2 Перестановки
Нехай ми маємо 4 компоненти, позначені літерами A, B, C, D відповідно.
Тоді множина всіх перестановок з цих компонент буде включати наступні елементи:
ABCD BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADBC BDAC CDAB DCAB
ADCB BDCA CDBA DCBA
Проілюструємо спочатку алгоритм побудови наступної перестановки на прикладі перестановок з 9 компонент, позначених відповідно цифрами від 1 до 9.
Перша з таких перестановок це
1 2 3 4 5 6 7 8 9
Нехай поточна перестановка з 9 компонент:
1 9 5 8 4 7 6 3 2
Яким буде таке значення перестановки, якщо ми будуємо її в лексикографічному порядку (тобто в порядку зростання величини числа, складеного з цих цифр)?
Правильна відповідь така:
1 9 5 8 6 2 3 4 7
Як він виходить?
Перш за все, необхідно переглядати вихідний масив від кінця до початку, що б знайти перше число, яке МЕНШЕ попереднього в нашому випадку - це 4
(7> 6> 3> 2, а 4 <7)
Далі серед переглянутих чисел праворуч від знайденої 4 ми шукаємо останнє число яке більше 4. Це число 6.
(7> 4, 6> 4, 3 <4, 2 <4)
Потім міняємо ці 2 знайдених числа (4 і 6) місцями, отримуємо:
1 9 5 8 6 7 4 3 2
І тепер числа (праворуч від 6), які становлять убуваючу послідовність (7 4 3 2), попарно міняємо місцями так, що б вони склали зростаючу послідовність (2 3 4 7):
1 9 5 8 6 2 3 4 7
Це і є наступна перестановка.
А яка перестановка буде останньою для даного прикладу?
Сподіваюся, що вдумливий читач здогадався і сам:
9 8 7 6 5 4 3 2 1
Кілька неформально алгоритм побудови наступної перестановки за поточною може бути записаний таким чином:
1. Від кінця до початку перестановки шукаємо перший елемент B [i] такий, що B [i] <B [i +1] запам'ятовуємо його індекс - I
2. Від елемента I +1 до кінця шукаємо останній елемент, більший ніж B [i], запам'ятовуємо його індекс - K
3. Міняємо місцями ці елементи - з номерами I і K
4. Всю групу елементів від i +1- го елемента до N-го попарно міняємо місцями (i +1- ий елемент з N-им, i +2- ой елемент з N-1-им і т.д.)
Формалізовано алгоритм генерації всіх перестановок з N елементів може бути записаний таким чином:
Введення N
Прописуємо масив B послідовно числами від 1 до N
Це перша - початкова - перестановка, виводимо її
Поки (істина)
i = N
Поки (i> 0) і (B [i]> = B [i +1]), i = i-1
Якщо i = 0 то кінець роботи
Для j від i +1 до N
якщо B [j]> B [i] то K = j
Обмін значень B [i] і B [k]
Для j від i +1 до (i + ((N +1- i) div 2))
Обмін значень B [j] і B [N + i +1- j]
Висновок поточної перестановки B
Зрозуміло, що цикл попарних перестановок "хвоста" масиву B не можна робити від i +1 до N-го елемента - інакше елементи поміняються місцями по 2 рази - і вийти, що нічого не змінилося. Цикл потрібно виконати для половини цього "хвоста". Цьому і служить декілька складний для розуміння значення кінцевої змінної циклу: i + (N +1- i) div 2
Нижче наводиться програма, що генерує всі перестановки з N компонент, позначених N першими літерами латинського алфавіту.
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i, j, k: byte;
Procedure SwapB (i, k: byte);
var x: byte;
begin
x: = B [i]; B [i]: = B [k]; B [k]: = x;
end;
Procedure WriteB;
begin
for i: = 1 to N do write ({alphabet [b [i]]);
writeln;
end;
begin
readln (N);
for i: = 1 to N do b [i]: = i;
WriteB;
while (true) do
begin
i: = N;
while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;
if i = 0 then exit;
for j: = i +1 to N do
if (B [j]> B [i]) then K: = j;
SwapB (i, k);
for j: = i +1 to (i + ((N +1- i) div 2))
do SwapB (j, N + i +1- j);
writeB;
end;
end.
У програмі введено 2 процедури WriteB і SwapB.
Процедура WriteB викликається кожного разу, коли побудована чергова перестановка. У даній програмі процедура WriteB просто виводить відповідну послідовність латинських літер.
Процедура SwapB (i, k) введена для спрощення розуміння головної програми. SwapB просто обмінює значеннями два елементи масиву B - ті, які мають індекси, що відповідають значенням параметрів процедури i і k.
Процедура SwapB використовується в тексті програми два рази
1) При обміні значеннями двох знайдених елементів з індексами I і K.
2) При забезпеченні попарного обміну елементів "хвоста", в якому поточний елемент з індексом j обмінюється місцями зі своїм "партнером", що знаходиться на позиції N + i +1- j. Таким чином, I +1- ий елемент поміняється (при J = I +1) місцями з N-м елементом, I +2- ий елемент (при J = I +2) з N-1-им і т.д.
Загальне число перестановок з N елементів одно N! (Читається N факторіал). Нагадаємо, що N! = 1 * 2 * 3 *...* N
3 Сполучення
Нехай маємо 5 компонент, позначених латинськими літерами A, B, C, D, E відповідно.
Тоді всі сполучення з цих 5 компонент по 3, виписані в лексикографічному порядку (для літер і цифр від 1 до 5) будуть такі:
ABC 123
ABD 124
ABE 125
ACD 134
ACE 135
ADE 145
BCD 234
BCE 235
BDE 245
CDE 345
Неформально алгоритм генерації послідовності чисел у лексикографічному порядку можна записати наступним чином. Виберемо найменші M з наявних N чисел і випишемо їх у порядку зростання - і випишемо їх у порядку зростання - 1 2 3 - це початкове поєднання. Очевидно, що найбільші M чисел з наявних (3 4 5), виписані в порядку зростання, складуть останнє поєднання.
Для того, що б за поточним поєднанню отримувати наступне, можна поступати таким чином:
Знаходимо позицію в поточному поєднанні, на якій не варто останнє з можливих значень, і потім збільшуємо його на 1. А всі наступні елементи поєднання отримуємо збільшенням на 1 попереднього елемента поєднання.
Наприклад нехай поточне поєднання
1 3 5
Аналіз починаємо з останньої позиції поєднання.
5 - це останнє можливе значення, тому переходимо до попередньої позиції. 3 - це не останнє можливе значення для цієї позиції (яким є 4 в даному випадку). Тому ми його збільшуємо на 1 - отримуємо 4. А число в такій позиції отримуємо додатком 1 до цієї 4-ці - і отримуємо 5. Таким чином таке значення буде 1 4 5
Більш формалізовано цей алгоритм може бути записаний таким чином:
Введення N, M (з скільки, на скільки)
Заносимо в масив B числа від 1 до M
Це перше поєднання, виводимо його
Поки (істина)
i = M
Поки (i> 0) і (b [i] = N-m + i), i = i-1
Якщо i = 0 то робота завершена
B [i] = B [i] +1
Для j від i +1 до MB [j] = B [j-1] +1;
Висновок B - наступної перестановки
Нижче наводиться програма, яка зчитує з клавіатури значення N і M і виводить у лексикографічному порядку всі поєднання з N перший латинських літер за M.
uses crt;
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, M, i, j, k: byte;
Procedure WriteB;
begin
for i: = 1 to M do write (alphabet [b [i]]);
writeln;
end;
begin
readln (N, M);
for i: = 1 to M do b [i]: = i;
WriteB;
while (true) do
begin
i: = M;
while (i> 0) and (b [i] = N-m + i) do Dec (i);
if i = 0 then exit;
Inc (B [i]);
for j: = i +1 to M do B [j]: = B [j-1] +1;
WriteB;
end;
end.
Нагадаємо, що загальна кількість сполучень з N елементів по M може бути обчислено за формулою C (N, M) = N! / (M! * (NM)!)
4 Розміщення
Для генерації всіх розміщень з N елементів з M можна скористатися композицією алгоритмів, викладених вище. Тобто генерувати всі сполучення з N з M, а потім для кожного отриманого поєднання генерувати всі перестановки з M елементів.
Наприклад, при генерації всіх розміщень з 5 елементів по 3, у випадку, якщо самі елементи позначені латинськими літерами A, B, C, D, E потрібно отримати наступну послідовність, представлену для компактності у вигляді 10 рядків, кожна з яких представляє всі можливі поєднання з 3 букв першого елемента рядка. А самі перші елементи рядків якраз і представляють всі можливі поєднання з 5 літер по 3.
ABC ACB BAC BCA CAB CBA
ABD ...
ABE ...
ACD ...
ACE ...
ADE ...
BCD ...
BCE ...
BDE ...
CDE CED DCE DEC ECD EDC
Загальна кількість pазмещеній - з N елементів по M може бути
знайдено за формулою:
N! / (NM)!
Нижче наводиться програма, яка вводить з клавіатури числа N, M і генерує всі можливі розміщення з N літер за M.
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
type
barray = array [1 .. 100] of byte;
var
b: barray;
N, M, i, j, k: byte;
z: longint;
Procedure WriteB (B: barray);
begin
Inc (Z); Write (Z: 3, ':');
for i: = 1 to M do write (alphabet [b [i]]);
writeln;
end;
Procedure SwapB (var B: barray; i, k: byte);
var x: byte;
begin
x: = B [i]; B [i]: = B [k]; B [k]: = x;
end;
Procedure PermuteAll (B: barray; N: byte);
var i, k, j: byte;
begin
WriteB (B);
while (true) do
begin
i: = N;
while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;
if i = 0 then exit;
for j: = i +1 to N do
if (B [j]> B [i]) then K: = j;
SwapB (B, i, k);
for j: = i +1 to (i + ((N +1- i) div 2)) do SwapB (B, j, N + i +1- j);
WriteB (B);
end;
end;
begin
readln (N, M);
for i: = 1 to M do b [i]: = i;
PermuteAll (B, M);
while (true) do
begin
i: = M;
while (i> 0) and (b [i] = N-m + i) do Dec (i);
if i = 0 then exit;
Inc (B [i]);
for j: = i +1 to M do B [j]: = B [j-1] +1;
PermuteAll (B, M);
end;
readln;
end.
Пояснення до програми:
1. Головна програма вводить числа N, M і генерує за описаним вище алгоритмом всі сполучення з N за M. Для кожного побудованого у векторі B поєднання викликається процедура PermuteAll, якій в якості параметрів передаються поточне поєднання B і кількість елементів у ньому M. Процедура PermuteAll генерує для отриманого поєднання всі можливі перестановки.
2. Масив B передається в процедуру PermuteAll за значенням (при оголошенні процедури при параметрі B немає ключового слова VAR) і тому зміни масиву B у процедурі PermuteAll не впливають на вміст масиву B у головній програмі.
3. У той же час для того, що б процедура SwapB могла обмінювати значення в B і повертати змінений масив в зухвалу її процедуру PermuteAll, масив B доданий в параметри процедури SwapB з передачею за адресою - використовуючи ключове слово VAR.
4. Для передачі масиву як параметра заведений спеціальний тип BARRAY.
5. Для підрахунку всіх згенерованих розміщень використовується змінна Z у процедурі WriteB.
5 Перестановки з повтореннями
Перестановки з повтореннями допускають повторне використання елементів. Наприклад, нехай маємо безліч, що складається з двох символів A та двох символів B.
Тоді всі перестановки з повтореннями з цих символів будуть такі:
AABB ABBA BABA ABAB BAAB BBAA
У загальному випадку, якщо маємо
N1 предметів 1-го виду
N2 предметів 2-го виду
...
Nk предметів K-го виду
Загальна кількість перестановок може бути обчислено за формулою
N! / (N1! * N2 !*..* Nk!)
Алгоритм аналогічний генерації перестановок без повторень за винятком формування початкової перестановки:
i = 0;
Для j від 1 до k
Для m від 1 до N [j] i = i +1; B [i] = j;
Нижче наводиться програма генерації перестановок з поверненнями. Кількість K різних типів предметів, позначених латинськими літерами вводиться з клавіатури. З клавіатури також вводяться кількості NN [j] предметів кожного типу.
Сума введених NN [j] визначає загальну кількість елементів у кожній з генеруються перестановок.
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i, j, k, m: byte;
NN: array [1 .. 100] of longint;
Procedure SwapB (i, k: byte);
var x: byte;
begin
x: = B [i]; B [i]: = B [k]; B [k]: = x;
end;
Procedure WriteB;
begin
for i: = 1 to N do write (alphabet [b [i]]);
writeln;
end;
begin
readln (K);
N: = 0;
for i: = 1 to K do
begin read (NN [i]); N: = N + NN [i]; end;
i: = 0;
for j: = 1 to k do
for m: = 1 to NN [j]
do begin Inc (i); B [i]: = j; end;
WriteB;
while (true) do
begin
i: = N;
while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;
if i = 0 then exit;
for j: = i +1 to N do if (B [j]> B [i]) then K: = j;
SwapB (i, k);
for j: = i +1 to (i + ((N +1- i) div 2)) do SwapB (j, N + i +1- j);
WriteB;
end;
end.
6 Сполучення з повтореннями
Для безлічі символів від A до C і розміру M = 3 поєднання з повтореннями будуть наступними:
CCC BCC BBC BBB ACC ABC ABB AAC AAB AAA
Загальна кількість сполучень = (N + M-1)! / (M! * (N-1)!)
де N - кількість символів
M - по скільки символів у поєднанні
Основна ідея створення таких сполучень з повтореннями полягає в наступному:
Сполучення записуємо у вигляді (N-1)-го нуля і M одиниць, де одиниці замінюють символи, а нулі виступають в pолі pазделітелей.
Наприклад:
ABB - 1 0 1 1 AAC - 1 1 0 0 1 CCC - 0 0 1 1 1
ABBAACCCC
При такому підході для вирішення завдання досить згенерувати всі перестановки з M одиниць і N-1-го нуля.
Нижче наводиться програма, яка вирішує поставлену задачу.
const
alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b: array [1 .. 100] of byte;
N, i, j, k, M, N1: byte;
Procedure SwapB (i, k: byte);
var x: byte;
begin
x: = B [i]; B [i]: = B [k]; B [k]: = x;
end;
Procedure WriteB;
var i, j: byte;
begin
j: = 1;
for i: = 1 to N do
if b [i] = 0
then Inc (j)
else write (alphabet [j]);
writeln;
end;
begin
readln (N1, M); N: = N1-1 + M;
for i: = 1 to n1-1 do b [i]: = 0;
for i: = n1 to n1 + m-1 do b [i]: = 1;
WriteB;
while (true) do
begin
i: = N;
while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;
if i = 0 then exit;
for j: = i +1 to N do
if (B [j]> B [i]) then K: = j;
SwapB (i, k);
for j: = i +1 to (i + ((N +1- i) div 2)) do
SwapB (j, N + i +1- j);
WriteB;
end;
end.
Пояснення до програми:
1. Початкова перестановка формується послідовно з N1-1 нулів і M одиниць.
2. У програмі виведення перестановки WriteB здійснені зміни, відповідні задумом (нулі - роздільники, одиниці - символи). Якщо поточний елемент масиву B дорівнює 0, то "стає активним" наступний символ. Якщо поточний символ масиву B дорівнює 1, то поточний активний символ виводиться на екран.
Висновок
Всі програми для більшої наочності в якості ілюстрації оперують з масивом символів від A до Z. Очевидно, що пропоновані алгоритми та програми практично не змінюються при роботі з масивами елементів будь-якого типу, необхідної за умовами задачі (наприклад, масивами чисел, слів, геометричних фігур і т.д.)
Література
1. Абдеев Р.Ф. Філософія інформаційної цивілізації. - М.: Владос, 1994.
2. Адамар Ж. Дослідження психології процесу винаходи в галузі математики. - М.: Сов. радіо, 1970.
3. Болтянский В.Г. Інформатика і математики / / Математика в школі. 1989. № 4.-С.86-90
4. Вейценбаум Дж. Можливості обчислювальних машин і людський розум. - М.: Радіо і зв'язок, 1982.
5. Вірт Н. Алгоритми + Структури даних = Програма. - М.: Світ, 1989
6. Вірт Н. Систематичне програмування: Введення. - М.: Світ, 1977.
7. Громов Г.Р. Нариси інформаційної технології. - М.: ІнфоАрт, 1993.
8. Дейкстра Е. Дисципліна програмування. - М.: Світ, 1978.
9. Ільєнко Е. В. Філософія і культура. - М.: Політ. лит., 1991.
10. Йодан Е. Структурне проектування і конструювання програм. - М.: Світ, 1979.
11. Майерс Г. Надійність програмного забезпечення. - М.: Світ, 1980.
12. Махмутов М.І. Організація проблемного навчання в школі. - М., 1986.